Mi manual de algoritmos/version_actual/src/grafos/ford_fulkerson_sparse.tex

   1 % Generator: GNU source-highlight, by Lorenzo Bettini, http://www.gnu.org/software/src-highlite
   2 {\ttfamily \raggedright {
   3 \noindent
   4 \mbox{}\textit{\textcolor{Brown}{////////////////\ Maximum\ flow\ for\ sparse\ graphs\ ////////////////}} \\
   5 \mbox{}\textit{\textcolor{Brown}{////////////////\ \ \ \ Complexity:\ O(V\ *\ E\textasciicircum{}2)\ \ \ \ \ \ ////////////////}} \\
   6 \mbox{} \\
   7 \mbox{}\textit{\textcolor{Brown}{/*}} \\
   8 \mbox{}\textit{\textcolor{Brown}{\ \ Usage:}} \\
   9 \mbox{}\textit{\textcolor{Brown}{\ \ initialize$\_$max$\_$flow();}} \\
  10 \mbox{}\textit{\textcolor{Brown}{\ \ Create\ graph\ using\ add$\_$edge(u,\ v,\ c);}} \\
  11 \mbox{}\textit{\textcolor{Brown}{\ \ max$\_$flow(source,\ sink);}} \\
  12 \mbox{} \\
  13 \mbox{}\textit{\textcolor{Brown}{\ \ WARNING:\ The\ algorithm\ writes\ on\ the\ cap\ array.\ The\ capacity\ is\ not}} \\
  14 \mbox{}\textit{\textcolor{Brown}{\ \ the\ same\ after\ having\ run\ the\ algorithm.\ \ If\ you\ need\ to\ run\ the}} \\
  15 \mbox{}\textit{\textcolor{Brown}{\ \ algorithm\ several\ times\ on\ the\ same\ graph,\ backup\ the\ cap\ array.}} \\
  16 \mbox{}\textit{\textcolor{Brown}{\ */}} \\
  17 \mbox{} \\
  18 \mbox{}\textbf{\textcolor{Blue}{const}}\ \textcolor{ForestGreen}{int}\ MAXE\ \textcolor{BrickRed}{=}\ \textcolor{Purple}{50000}\textcolor{BrickRed}{;}\ \textit{\textcolor{Brown}{//Maximum\ number\ of\ edges}} \\
  19 \mbox{}\textbf{\textcolor{Blue}{const}}\ \textcolor{ForestGreen}{int}\ oo\ \textcolor{BrickRed}{=}\ INT$\_$MAX\ \textcolor{BrickRed}{/}\ \textcolor{Purple}{4}\textcolor{BrickRed}{;} \\
  20 \mbox{}\textcolor{ForestGreen}{int}\ cap\textcolor{BrickRed}{[}MAXE\textcolor{BrickRed}{];} \\
  21 \mbox{}\textcolor{ForestGreen}{int}\ first\textcolor{BrickRed}{[}MAXE\textcolor{BrickRed}{];} \\
  22 \mbox{}\textcolor{ForestGreen}{int}\ next\textcolor{BrickRed}{[}MAXE\textcolor{BrickRed}{];} \\
  23 \mbox{}\textcolor{ForestGreen}{int}\ adj\textcolor{BrickRed}{[}MAXE\textcolor{BrickRed}{];} \\
  24 \mbox{}\textcolor{ForestGreen}{int}\ current$\_$edge\textcolor{BrickRed}{;} \\
  25 \mbox{} \\
  26 \mbox{}\textit{\textcolor{Brown}{/*}} \\
  27 \mbox{}\textit{\textcolor{Brown}{\ \ Builds\ a\ directed\ edge\ (u,\ v)\ with\ capacity\ c.}} \\
  28 \mbox{}\textit{\textcolor{Brown}{\ \ Note\ that\ actually\ two\ edges\ are\ added,\ the\ edge}} \\
  29 \mbox{}\textit{\textcolor{Brown}{\ \ and\ its\ complementary\ edge\ for\ the\ backflow.}} \\
  30 \mbox{}\textit{\textcolor{Brown}{\ */}} \\
  31 \mbox{}\textcolor{ForestGreen}{int}\ \textbf{\textcolor{Black}{add$\_$edge}}\textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ u\textcolor{BrickRed}{,}\ \textcolor{ForestGreen}{int}\ v\textcolor{BrickRed}{,}\ \textcolor{ForestGreen}{int}\ c\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  32 \mbox{}\ \ adj\textcolor{BrickRed}{[}current$\_$edge\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ v\textcolor{BrickRed}{;} \\
  33 \mbox{}\ \ cap\textcolor{BrickRed}{[}current$\_$edge\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ c\textcolor{BrickRed}{;} \\
  34 \mbox{}\ \ next\textcolor{BrickRed}{[}current$\_$edge\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ first\textcolor{BrickRed}{[}u\textcolor{BrickRed}{];} \\
  35 \mbox{}\ \ first\textcolor{BrickRed}{[}u\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ current$\_$edge\textcolor{BrickRed}{++;} \\
  36 \mbox{} \\
  37 \mbox{}\ \ adj\textcolor{BrickRed}{[}current$\_$edge\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ u\textcolor{BrickRed}{;} \\
  38 \mbox{}\ \ cap\textcolor{BrickRed}{[}current$\_$edge\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ \textcolor{Purple}{0}\textcolor{BrickRed}{;} \\
  39 \mbox{}\ \ next\textcolor{BrickRed}{[}current$\_$edge\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ first\textcolor{BrickRed}{[}v\textcolor{BrickRed}{];} \\
  40 \mbox{}\ \ first\textcolor{BrickRed}{[}v\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ current$\_$edge\textcolor{BrickRed}{++;} \\
  41 \mbox{}\textcolor{Red}{\}} \\
  42 \mbox{} \\
  43 \mbox{}\textcolor{ForestGreen}{void}\ \textbf{\textcolor{Black}{initialize$\_$max$\_$flow}}\textcolor{BrickRed}{()}\textcolor{Red}{\{} \\
  44 \mbox{}\ \ current$\_$edge\ \textcolor{BrickRed}{=}\ \textcolor{Purple}{0}\textcolor{BrickRed}{;} \\
  45 \mbox{}\ \ \textbf{\textcolor{Black}{memset}}\textcolor{BrickRed}{(}next\textcolor{BrickRed}{,}\ \textcolor{BrickRed}{-}\textcolor{Purple}{1}\textcolor{BrickRed}{,}\ \textbf{\textcolor{Blue}{sizeof}}\ next\textcolor{BrickRed}{);} \\
  46 \mbox{}\ \ \textbf{\textcolor{Black}{memset}}\textcolor{BrickRed}{(}first\textcolor{BrickRed}{,}\ \textcolor{BrickRed}{-}\textcolor{Purple}{1}\textcolor{BrickRed}{,}\ \textbf{\textcolor{Blue}{sizeof}}\ first\textcolor{BrickRed}{);} \\
  47 \mbox{}\textcolor{Red}{\}} \\
  48 \mbox{} \\
  49 \mbox{}\textcolor{ForestGreen}{int}\ q\textcolor{BrickRed}{[}MAXE\textcolor{BrickRed}{];} \\
  50 \mbox{}\textcolor{ForestGreen}{int}\ incr\textcolor{BrickRed}{[}MAXE\textcolor{BrickRed}{];} \\
  51 \mbox{}\textcolor{ForestGreen}{int}\ arrived$\_$by\textcolor{BrickRed}{[}MAXE\textcolor{BrickRed}{];}\ \textit{\textcolor{Brown}{//arrived$\_$by[i]\ =\ The\ last\ edge\ used\ to\ reach\ node\ i}} \\
  52 \mbox{}\textcolor{ForestGreen}{int}\ \textbf{\textcolor{Black}{find$\_$augmenting$\_$path}}\textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ src\textcolor{BrickRed}{,}\ \textcolor{ForestGreen}{int}\ snk\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  53 \mbox{}\ \ \textit{\textcolor{Brown}{/*}} \\
  54 \mbox{}\textit{\textcolor{Brown}{\ \ \ \ Make\ a\ BFS\ to\ find\ an\ augmenting\ path\ from\ the\ source\ to\ the\ sink.}} \\
  55 \mbox{}\textit{\textcolor{Brown}{\ \ \ \ Then\ pump\ flow\ through\ this\ path,\ and\ return\ the\ amount\ that\ was\ pumped.}} \\
  56 \mbox{}\textit{\textcolor{Brown}{\ \ */}} \\
  57 \mbox{}\ \ \textbf{\textcolor{Black}{memset}}\textcolor{BrickRed}{(}arrived$\_$by\textcolor{BrickRed}{,}\ \textcolor{BrickRed}{-}\textcolor{Purple}{1}\textcolor{BrickRed}{,}\ \textbf{\textcolor{Blue}{sizeof}}\ arrived$\_$by\textcolor{BrickRed}{);} \\
  58 \mbox{}\ \ \textcolor{ForestGreen}{int}\ h\ \textcolor{BrickRed}{=}\ \textcolor{Purple}{0}\textcolor{BrickRed}{,}\ t\ \textcolor{BrickRed}{=}\ \textcolor{Purple}{0}\textcolor{BrickRed}{;} \\
  59 \mbox{}\ \ q\textcolor{BrickRed}{[}t\textcolor{BrickRed}{++]}\ \textcolor{BrickRed}{=}\ src\textcolor{BrickRed}{;} \\
  60 \mbox{}\ \ arrived$\_$by\textcolor{BrickRed}{[}src\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ \textcolor{BrickRed}{-}\textcolor{Purple}{2}\textcolor{BrickRed}{;} \\
  61 \mbox{}\ \ incr\textcolor{BrickRed}{[}src\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ oo\textcolor{BrickRed}{;} \\
  62 \mbox{}\ \ \textbf{\textcolor{Blue}{while}}\ \textcolor{BrickRed}{(}h\ \textcolor{BrickRed}{$<$}\ t\ \textcolor{BrickRed}{\&\&}\ arrived$\_$by\textcolor{BrickRed}{[}snk\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{==}\ \textcolor{BrickRed}{-}\textcolor{Purple}{1}\textcolor{BrickRed}{)}\textcolor{Red}{\{}\ \textit{\textcolor{Brown}{//BFS}} \\
  63 \mbox{}\ \ \ \ \textcolor{ForestGreen}{int}\ u\ \textcolor{BrickRed}{=}\ q\textcolor{BrickRed}{[}h\textcolor{BrickRed}{++];} \\
  64 \mbox{}\ \ \ \ \textbf{\textcolor{Blue}{for}}\ \textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ e\ \textcolor{BrickRed}{=}\ first\textcolor{BrickRed}{[}u\textcolor{BrickRed}{];}\ e\ \textcolor{BrickRed}{!=}\ \textcolor{BrickRed}{-}\textcolor{Purple}{1}\textcolor{BrickRed}{;}\ e\ \textcolor{BrickRed}{=}\ next\textcolor{BrickRed}{[}e\textcolor{BrickRed}{])}\textcolor{Red}{\{} \\
  65 \mbox{}\ \ \ \ \ \ \textcolor{ForestGreen}{int}\ v\ \textcolor{BrickRed}{=}\ adj\textcolor{BrickRed}{[}e\textcolor{BrickRed}{];} \\
  66 \mbox{}\ \ \ \ \ \ \textbf{\textcolor{Blue}{if}}\ \textcolor{BrickRed}{(}arrived$\_$by\textcolor{BrickRed}{[}v\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{==}\ \textcolor{BrickRed}{-}\textcolor{Purple}{1}\ \textcolor{BrickRed}{\&\&}\ cap\textcolor{BrickRed}{[}e\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{$>$}\ \textcolor{Purple}{0}\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  67 \mbox{}\ \ \ \ \ \ \ \ arrived$\_$by\textcolor{BrickRed}{[}v\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ e\textcolor{BrickRed}{;} \\
  68 \mbox{}\ \ \ \ \ \ \ \ incr\textcolor{BrickRed}{[}v\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ \textbf{\textcolor{Black}{min}}\textcolor{BrickRed}{(}incr\textcolor{BrickRed}{[}u\textcolor{BrickRed}{],}\ cap\textcolor{BrickRed}{[}e\textcolor{BrickRed}{]);} \\
  69 \mbox{}\ \ \ \ \ \ \ \ q\textcolor{BrickRed}{[}t\textcolor{BrickRed}{++]}\ \textcolor{BrickRed}{=}\ v\textcolor{BrickRed}{;} \\
  70 \mbox{}\ \ \ \ \ \ \textcolor{Red}{\}} \\
  71 \mbox{}\ \ \ \ \textcolor{Red}{\}} \\
  72 \mbox{}\ \ \textcolor{Red}{\}} \\
  73 \mbox{} \\
  74 \mbox{}\ \ \textbf{\textcolor{Blue}{if}}\ \textcolor{BrickRed}{(}arrived$\_$by\textcolor{BrickRed}{[}snk\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{==}\ \textcolor{BrickRed}{-}\textcolor{Purple}{1}\textcolor{BrickRed}{)}\ \textbf{\textcolor{Blue}{return}}\ \textcolor{Purple}{0}\textcolor{BrickRed}{;} \\
  75 \mbox{} \\
  76 \mbox{}\ \ \textcolor{ForestGreen}{int}\ cur\ \textcolor{BrickRed}{=}\ snk\textcolor{BrickRed}{;} \\
  77 \mbox{}\ \ \textcolor{ForestGreen}{int}\ neck\ \textcolor{BrickRed}{=}\ incr\textcolor{BrickRed}{[}snk\textcolor{BrickRed}{];} \\
  78 \mbox{}\ \ \textbf{\textcolor{Blue}{while}}\ \textcolor{BrickRed}{(}cur\ \textcolor{BrickRed}{!=}\ src\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  79 \mbox{}\ \ \ \ \textit{\textcolor{Brown}{//Remove\ capacity\ from\ the\ edge\ used\ to\ reach\ node\ "{}cur"{}}} \\
  80 \mbox{}\ \ \ \ \textit{\textcolor{Brown}{//Add\ capacity\ to\ the\ backedge}} \\
  81 \mbox{}\ \ \ \ cap\textcolor{BrickRed}{[}arrived$\_$by\textcolor{BrickRed}{[}cur\textcolor{BrickRed}{]]}\ \textcolor{BrickRed}{-=}\ neck\textcolor{BrickRed}{;} \\
  82 \mbox{}\ \ \ \ cap\textcolor{BrickRed}{[}arrived$\_$by\textcolor{BrickRed}{[}cur\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{\textasciicircum{}}\ \textcolor{Purple}{1}\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{+=}\ neck\textcolor{BrickRed}{;} \\
  83 \mbox{}\ \ \ \ cur\ \textcolor{BrickRed}{=}\ adj\textcolor{BrickRed}{[}arrived$\_$by\textcolor{BrickRed}{[}cur\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{\textasciicircum{}}\ \textcolor{Purple}{1}\textcolor{BrickRed}{];}\ \textit{\textcolor{Brown}{//move\ backwards\ in\ the\ path}} \\
  84 \mbox{}\ \ \textcolor{Red}{\}} \\
  85 \mbox{}\ \ \textbf{\textcolor{Blue}{return}}\ neck\textcolor{BrickRed}{;} \\
  86 \mbox{}\textcolor{Red}{\}} \\
  87 \mbox{} \\
  88 \mbox{}\textcolor{ForestGreen}{int}\ \textbf{\textcolor{Black}{max$\_$flow}}\textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ src\textcolor{BrickRed}{,}\ \textcolor{ForestGreen}{int}\ snk\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  89 \mbox{}\ \ \textcolor{ForestGreen}{int}\ ans\ \textcolor{BrickRed}{=}\ \textcolor{Purple}{0}\textcolor{BrickRed}{,}\ neck\textcolor{BrickRed}{;} \\
  90 \mbox{}\ \ \textbf{\textcolor{Blue}{while}}\ \textcolor{BrickRed}{((}neck\ \textcolor{BrickRed}{=}\ \textbf{\textcolor{Black}{find$\_$augmenting$\_$path}}\textcolor{BrickRed}{(}src\textcolor{BrickRed}{,}\ snk\textcolor{BrickRed}{))}\ \textcolor{BrickRed}{!=}\ \textcolor{Purple}{0}\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  91 \mbox{}\ \ \ \ ans\ \textcolor{BrickRed}{+=}\ neck\textcolor{BrickRed}{;} \\
  92 \mbox{}\ \ \textcolor{Red}{\}} \\
  93 \mbox{}\ \ \textbf{\textcolor{Blue}{return}}\ ans\textcolor{BrickRed}{;} \\
  94 \mbox{}\textcolor{Red}{\}} \\
  95 \mbox{}
  96 } \normalfont\normalsize